Nathaniel Edward Story (August 8, 1904, Oak Station, Kentucky - November 21, 1968, Evansville, Indiana) was an American jazz trombonist.
Story played on riverboats on the Mississippi with Fate Marable and Floyd Campbell in the 1920s, and played with the Jones and Collins Astoria Hot Eight in 1928. He moved to New York City in the 1930s, working with Luis Russell (1934), Sam Wooding (1934), and Chick Webb (1936-39). After Webb's death he remained in the orchestra under the direction of Ella Fitzgerald, but left in 1940. Early in the 1940s he played with Andy Kirk and Lucky Millinder, but went into semi-retirement after this, though he performed occasionally into the 1960s.